#include "bst.h"
#include <queue>
#include <stack>
#include <iostream>
#include <unistd.h>

static BST::Node * copy_tree( const BST::Node * other ) {
    if(other == nullptr)
        return nullptr;

    BST::Node * new_root = new BST::Node();
    new_root->value = other->value;

    new_root->left  = copy_tree(other->left);
    new_root->right = copy_tree(other->right);

    return new_root;
}

BST::BST( const BST & other) {
    num = other.num;
    root = copy_tree(other.root);
}

BST::BST( BST && other ) noexcept : 
    root(other.root) , num(other.num) {
        other.num = 0;
        other.root = nullptr;
}

BST::BST( std::initializer_list<int>  list  ) {
    root = nullptr;
    num = 0;
    std::vector<int> i{list};
    for( auto a : i ) {
        add_node(a);
    }
}

BST& BST::operator=( const BST & other ) {
    if( this == &other )
        return *this;
    num = other.num;
    root = copy_tree(other.root);
    return *this;
};

static void free_tree( BST::Node * tree ) {
    if( tree == nullptr )
        return;
    free_tree(tree->left);
    free_tree(tree->right);
    delete tree;

    return;
}

BST::~BST()
{
	//std::cout << "Destructor called" << std::endl;
    if( root != nullptr )
        free_tree(root);
}

BST& BST::operator=( BST && other ) {
    //std::cout << &other << std::endl;
    if( this == &other ) {
        return *this;
    }
    num = other.num;
    root = other.root;

    other.num = 0;
    other.root= nullptr;

    return *this;
}
static void tree_self_increase( BST::Node * tree ) {
    if( tree ==nullptr ) // do nothing
        return;
    tree->value ++;
    tree_self_increase(tree->left );
    tree_self_increase(tree->right);
    return;
}

BST& BST::operator++() {
    tree_self_increase(root);
    return *this;
}

BST BST::operator++(int fxxk_cpp) {
    BST temp(*this);
    tree_self_increase(root);
    return temp;
}

std::ostream& operator<<(std::ostream& os , const BST& tree ) {
    std::stringstream ss;
    if( tree.root == nullptr ) {
        ss << "(EMPTY TREE)" << std::endl;
    }
    else {
        std::stack<BST::Node *> nstack;
        nstack.push(tree.root);
        while (!nstack.empty()) {
            // middle-order travelsal
            BST::Node * top = nstack.top(); 
            if( top->left ) {
                nstack.push(top->left);
            }
            else {
                while(!nstack.empty()) {
                    ss << *top;
                    nstack.pop();
                    if( top->right ) {
                        ss << std::endl;
                        nstack.push(top->right);
                        break;
                    }
                    if (!nstack.empty()) {
                        ss << std::endl;
                        top = nstack.top();
                    }
                }
            }
        }
    }
    os << ss.str();
    return os;
}


bool BST::add_node(int value) {
    if( root == nullptr ) {
        Node * n = new Node(value,nullptr,nullptr);
        root = n;
        num++;
        return true;
    }
    else {
        Node * nptr = root;
        while (true) {
            if( nptr->value == value ) {
                return false;
            }
            else if( value < nptr->value ){
                if( nptr ->left == nullptr ) {
                    Node *n = new Node(value,nullptr,nullptr);
                    nptr->left = n;
                    num++;
                    return true;
                }
                else {
                    nptr = nptr->left;
                }
            }
            else {
                if( nptr->right == nullptr) {
                    Node *n = new Node(value,nullptr,nullptr);
                    nptr->right = n;
                    num++;
                    return true;
                }
                else {
                    nptr = nptr->right;
                }
            }
        }
    }
}

void BST::bfs(std::function<void(Node* &node)> func) {
    if( root == nullptr )
        return;
    std::queue<Node *> qn;
    qn.push(root);
    while(!qn.empty()) {
        Node * now = qn.front();
        qn.pop();
        func(now);
        if(now->left)  qn.push(now->left );
        if(now->right) qn.push(now->right);
    }
    return;
}
BST::Node ** BST::find_node (int value) {
    Node ** ret = nullptr;
    if( root == nullptr )
        return nullptr;
    if( root ->value == value)
        return &root;
    Node * nptr = root;
    while (nptr != nullptr) {
        if( value < nptr->value ) {
            if( nptr->left ) {
                if( nptr->left->value == value ) {
                    ret = &(nptr->left);
                    break;
                }
                else
                    nptr = nptr->left;
            }
            else {
                ret = nullptr;
                break;
            }
        }
        else {
            if( nptr->right ) {
                if( nptr->right->value == value ) {
                    ret = &(nptr->right);
                    break;
                }
                else
                    nptr = nptr->right;
            }
            else {
                ret = nullptr;
                break;
            }
        }
    }
    return ret;
}

BST::Node** BST::find_parrent(int value) {
    Node ** ret = nullptr;
    if( root == nullptr )
        return nullptr;
    if( root -> value == value)
        return nullptr;

    Node** npptr = &root;
    while (true) {
        Node * nptr = * npptr;
        if( nptr->value > value ) {
            // see left
            if( nptr->left ) {
                if( nptr->left-> value == value ) {
                    ret = npptr;
                    break;
                }
                else {
                    npptr = &(nptr->left);
                }
            }
            else {
                ret = nullptr;
                break;
            }
        }
        else {
            if( nptr -> right ) {
                if( nptr->right->value == value ) {
                    ret = npptr;
                    break;
                }
                else {
                    npptr = &(nptr->right);
                }
            }
            else {
                ret = nullptr;
                break;
            }
        }
    }
    return ret;
}

BST::Node** BST::find_successor(int value) {
    Node ** ret = nullptr;
    if( root == nullptr )
        return nullptr;
    ssize_t tar_idx = -1;
    std::stack<BST::Node **>   nstack;
    std::vector<BST:: Node **> Node_v;
    nstack.push(&root);
    while (!nstack.empty()) {
            // middle-order travelsal
            BST::Node ** topp = nstack.top();
            BST::Node * top = *topp;
            if( top->left ) {
                nstack.push( &(top->left));
            }
            else {
                while(!nstack.empty()) {
                    Node_v.push_back(topp);
                    if( value == (**topp).value) {
                        tar_idx = Node_v.size() - 1;
                        if( tar_idx == 0 )
                            return nullptr;
                        else
                            return Node_v[tar_idx - 1];
                    }
                    nstack.pop();
                    if( top->right ) {
                        nstack.push( &(top->right));
                        break;
                    }
                    if (!nstack.empty()) {
                        topp = nstack.top();
                    }
                }
            }
    }
    return nullptr;
}


bool BST::delete_node(int value) {
    if( root == nullptr )
        return false;

    if( root -> value == value ) {
        if( root->left == nullptr && root->right == nullptr ) {
            delete root;
            root = nullptr;

            num -- ;
            return true;
        }
        else if( root -> left  ) {
            Node * dptr = root;
            if( root->right == nullptr ) {
                root = root->left;
            }
            else {
                if( root->left->right == nullptr ) {
                    root->left->right = root->right;
                    root = root->left;
                }
                else {
                    Node * lmax_ahead = root->left;
                    while (lmax_ahead->right->right) {
                        lmax_ahead = lmax_ahead->right;
                    }
                    Node * lmax = lmax_ahead->right;
                    lmax_ahead->right = lmax->left;
    
                    lmax->left = root->left ;
                    lmax->right= root->right;
    
                    root = lmax;
                }
            }
            delete dptr;
            num--;
            return true;
        }
        else {
            Node * dptr = root;
            root = root -> right;
            delete dptr;
            num--;
            return true;
        }
    }

    Node * ptr = root;
    while (ptr) {
        Node * dptr = nullptr;
        Node **rptr = nullptr;
        if( ptr->left ) {
            if( ptr->left->value == value) {
                dptr = ptr->left;
                rptr = &(ptr->left);
            }
        }

        if(ptr->right) {
            if( ptr->right->value == value ) {
                dptr = ptr->right;
                rptr = &(ptr->right);
            }
        }

        if( dptr ) {
            if( dptr->left == nullptr && dptr->right == nullptr ) {
                *rptr = nullptr;

                delete dptr;
                num--;
                return true;
            }
            else if(dptr->left)  {
                if( dptr->right == nullptr ) {
                    *rptr = dptr->left;
                }
                else {
                    if( dptr->left->right == nullptr ) {
                        dptr->left->right = dptr->right;
                        *rptr = dptr->left;
                    }
                    else {
                        Node * lmax_ahead = dptr->left;
                        while (lmax_ahead->right->right) {
                            lmax_ahead = lmax_ahead->right;
                        }
    
                        Node * lmax = lmax_ahead->right;
                        lmax_ahead->right = lmax->left;
                    
                        lmax->left = dptr->left;
                        lmax->right=dptr->right;
    
                        *rptr = lmax;
                    }
                }
                delete dptr;
                num--;
                return true;
            }
            else {
                *rptr = dptr->right;
                delete dptr;
                num--;
                return true;
            }
        }
        else {
            if( value < ptr->value ) {
                ptr = ptr->left;
            }
            else if (value > ptr->value) {
                ptr = ptr->right;
            }
        }
    }
    return false;
}

